[Coding002] LeetCode 15

3Sum

More coding records

Get the knowledge flowing and circulating! :)

目录

题目：3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

xxxxxxxxxx
8
1
Input: nums = [-1,0,1,2,-1,-4]
2
Output: [[-1,-1,2],[-1,0,1]]
3
Explanation: 
4
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
5
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
6
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
7
The distinct triplets are [-1,0,1] and [-1,-1,2].
8
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

xxxxxxxxxx
3
1
Input: nums = [0,1,1]
2
Output: []
3
Explanation: The only possible triplet does not sum up to 0.

Example 3:

xxxxxxxxxx
3
1
Input: nums = [0,0,0]
2
Output: [[0,0,0]]
3
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000

• -105 <= nums[i] <= 105

解题

解题思路

• 一开始的想法是，从头到尾直接遍历，按照下标0 1 2，0 1 3， 0 1 4... 这样，但是因为数组中的数是乱序的，所以可能会很难排除重复元素。

• 所以，后来的想法变成： 先排序，然后再按照这种方法进行遍历！

代码

xxxxxxxxxx
31
1
// 错误代码
2
class Solution {
3
    public List<List<Integer>> threeSum(int[] nums) {
4
        List<List<Integer>> res = new ArrayList<>();
5

6
        Arrays.sort(nums);
7

8
        int n = nums.length;
9

10
        for(int i = 0; i < n; i++)
11
        {
12
            for(int j = i + 1; j < n; j++)
13
            {
14
                for (int k = j + 1; k < n; k++)
15
                {
16
                    if (nums[i] + nums[j] + nums[k] == 0)
17
                    {
18
                        List<Integer> temp = new ArrayList<>();
19
                        temp.add(nums[i]);
20
                        temp.add(nums[j]);
21
                        temp.add(nums[k]);
22

23
                        res.add(temp);
24
                    }
25
                }
26
            }
27
        }
28

29
        return res;
30
    }
31
}

// 错误原因：res中出现了重复的元素 // 分析：排序后的数组为[-4, -1, -1, 0, 1, 2], 所以遍历加入的话，会出现重复的元组[-1, 0, 1]

如何解决呢？

可不可以判断，res这个元素是否已经存在了即将加入的元素呢？

通过检索：确实，对于List这个类而言，有一个方法：

xxxxxxxxxx
1
1
boolean | contains(Object o) | Returns true if this list contains the specified element.

所以，这里把第23行改了。

xxxxxxxxxx
2
1
if(!res.contains(temp))
2
 res.add(temp);

可是，依然报错（有几个样例是过不了的，这样的方法太耗时了，追溯根源，猜测应该是List的内部实现可能太耗时了吧，目前就不深究了~）：

Time Limit Exceeded 308 / 312 testcases passed

所以继续寻找解决方法吧！

在网上看了一个视频，但是里面用的是c++实现的，然后我来改写了一下，但是始终没有通过，会报错。

xxxxxxxxxx
57
1
// 报错代码(仅用于记录自己当前的思维，以后回看的时候，可以供自己检视一下，看看自己的脑洞为啥没打开~)
2
class Solution {
3
    public List<List<Integer>> threeSum(int[] nums) {
4
        List<List<Integer>> res = new ArrayList<>();
5

6
        Arrays.sort(nums);
7

8
        int n = nums.length;
9

10
        Map<Integer, Integer> count = new HashMap<>();
11

12
        // 记录每个元素出现的次数
13
        for(int i = 0; i < n; i++)
14
        {
15
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
16
        }
17
 
18
        /*
19
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) 
20
        {        
21
            System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());        
22
        }
23
        */
24

25
        for (int i = 0; i < n; i++)
26
        {
27
            if (i != 0 && nums[i] == nums[i - 1]) continue;
28

29
            for (int j = i + 1; j < n; j++)
30
            {
31
                if (j - 1 != i && nums[j] != nums[j - 1]) continue;
32

33
                int temp = 0 - nums[i] - nums[j];
34
                
35
                if (temp < nums[j]) continue;
36
                if ((int)count.get(temp) == 0) continue;
37

38
                int c = 0;
39
                if (nums[i] == temp) c++;
40
                if (nums[j] == temp) c++;
41

42
                if (count.get(temp) >= 1 + c)
43
                {
44
                    List<Integer> cur = new ArrayList<>();
45
                    cur.add(nums[i]);                    
46
                    cur.add(nums[j]);
47
                    cur.add(temp);
48

49
                    res.add(cur);
50
                }
51

52
            }
53
        }
54

55
        return res;
56
    }
57
}

感受：

这个解法的视频，分析的确实有些道理，但是实在无法丝滑的想到这个想法，所以我的感受就是，如果现在遇到的解法，我还无法理解，就果断放弃，因为还有很多好的方法，不需要死磕这一种，或许我的认知还没达到，或者，这本身就是一个比较差的方法吧~ anyway, 反正就是再寻找别的方法吧。

※双指针解法：

xxxxxxxxxx
44
1
class Solution {
2
    public List<List<Integer>> threeSum(int[] nums) {
3
        List<List<Integer>> res = new ArrayList<>();
4

5
        Arrays.sort(nums);  // 排序
6

7
        int n = nums.length;
8

9
        for (int i = 0; i < n; i++)
10
        {
11
            // 下标[i - 1]不能为负数，所以i不能为0
12
            if (i != 0 && nums[i] == nums[i - 1]) continue; // continue是因为两个数相等，要跳过！
13

14
            int j = i + 1;  // 左指针
15
            int k = n - 1;  // 右指针
16

17
            while(j < k) //界
18
            {
19
                // 当第一个数选定之后，j向右滑动，k向左滑动
20
                if (nums[i] + nums[j] + nums[k] > 0) k--;
21
                else if (nums[i] + nums[j] + nums[k] < 0) j++;
22
                else // 刚好相等的时候
23
                {
24
                    List<Integer> temp = new ArrayList<>();
25
                    temp.add(nums[i]);
26
                    temp.add(nums[j]);
27
                    temp.add(nums[k]);
28

29
                    res.add(temp);  // 装载答案元组
30

31
                    while(j < k && nums[j] == nums[j + 1]) j++;  // 在固定的界内，如果下一个j和当前的j一样，就跳过；
32
                    while(j < k && nums[k] == nums[k - 1]) k--;  // 在固定的界内，如果上一个k和当前的k一样，就跳过；
33

34
                    // 缩小双指针范围：上一个j和k已经用过了，下面要继续往中间缩小范围找其他答案元组了！
35
                    j++; 
36
                    k--;
37
                }
38
            }
39
        }
40

41

42
        return res;
43
    }
44
}

还是同样的视频，这个解法更容易理解！

双指针的用法，很棒！

复杂度分析

双指针解法，第一个for循环，是O(n)

第二个循环，是从 i + 1 → n - 1, 所以范围也是O(n)

嵌套起来，复杂度就是$O(n^2)$$O(n^2)$

★ 知识点积累 (Java)

1. java的List用法

   xxxxxxxxxx
   13
   1
   List<List<Integer>> res = new ArrayList<>();
   2
   
   3
   // 如果嵌套的话，无法一条语句搞定，所以要拆开成两部分
   4
   List<Integer> temp = new ArrayList<>();
   5
   temp.add(nums[i]);
   6
   temp.add(nums[j]);
   7
   temp.add(nums[k]);
   8
   
   9
   res.add(temp);  // 装载答案元组
   10
   
   11
   // List本身带有contains方法
   12
   if(!res.contains(temp))
   13
       res.add(temp);
   

2. HashMap的计数方法 和 元素遍历方法

   xxxxxxxxxx
   12
   1
   // 记录每个元素出现的次数
   2
   for(int i = 0; i < n; i++)
   3
   {
   4
       count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
   5
   }
   6
   
   7
   // HashMap的元素遍历方法
   8
   for (Map.Entry<Integer, Integer> entry : count.entrySet()) 
   9
   {        
   10
       System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());        
   11
   }
   12
   
   

3. Java数组排序的自带函数

   xxxxxxxxxx
   1
   1
   Arrays.sort(nums);